package array.leetcode.easy;

/**
 * @author bruin_du
 * @description 在排序数组中查找数字 I
 * @date 2022/5/17 16:18
 **/
public class Offer53I_Search {

    int choice = 1;
    public int search(int[] nums, int target) {
        //用二分找到与target相同元素的边界,再返回中间元素的个数即可
        if(choice == 1){
            int left = 0,right = nums.length - 1;
            //找右边界
            while(left <= right){
                int mid = (right - left >> 1) + left;
                if(nums[mid] <= target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            //如果有多个与target相同的元素,left都往后,因为要找到边界值(不等于target)
            //而且肯定left先要等于right,才能出循环
            //所以right指向最后一个target,left指向target后的边界元素
            //如果这个数不等于target,说明数组里就没有,返回0
            if(right >= 0 && nums[right] != target)
                return 0;
            int retRight = left;
            //只用更新left即可,因为right后面的元素可以不用看了
            left = 0;
            //找左边界
            while(left <= right){
                int mid = (right - left >> 1) + left;
                if(nums[mid] < target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            //right指向左边界
            //left指向第一个target
            int retLeft = right;
            return retRight - retLeft - 1;
        }

        //方法一的再优化版本
        //两次使用二分查找可以把它封装为一个函数
        if(choice == 2){
            //找原target的下一个元素，即就是右边界
            //找target - 1的元素的右边界就是第一个target
            return searchHelper(nums,target) - searchHelper(nums,target - 1);
        }

        //因为数组是有序的,所以使用二分查找找到与目标相等的元素
        //在该元素上往前和往后找相同值的元素并记录个数
        //这种写法不好，极端情况下当目标和数组中元素全部想等的时候会退化为O(n),
        if(choice == 3) {
            if (nums.length == 0)
                return 0;
            int left = 0, right = nums.length - 1;
            int count = 0;
            while (left <= right) {
                int mid = (right - left >> 1) + left;
                if (nums[mid] < target)
                    left = mid + 1;
                else if (nums[mid] == target) {
                    int i = 0;
                    while (mid + i < nums.length && nums[mid + i] == target) {
                        count++;
                        i++;
                    }
                    i = 1;
                    while (mid + i < nums.length && nums[mid - i] == target) {
                        count++;
                        i++;
                    }
                    break;
                } else
                    right = mid - 1;
            }
            return count;
        }
        return -1;
    }

    private int searchHelper(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <= right){
            int mid = (right - left >> 1) + left;
            if(nums[mid] <= target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
}
